#include<iostream>
#include<vector>
#include<stdlib.h>
#include<algorithm>
using namespace std;

void display(vector<int> & vct){
    return;
    for(auto a:vct){
        cout << a<<' ';
    }
    cout << endl;
}

class RandInt{
    vector <int> arr;
    vector <int> arr_good;
    vector <int> arr_bad;
    int t;
public:
    RandInt(int sz,int m1,int m2){
        while (sz--)
        {
            t = rand() % (m2 - m1) + m1;
            arr.push_back(t);
            arr_good.push_back(t);
            arr_bad.push_back(t);
        }
        sort(arr_good.begin(),arr_good.end(),less<int>());
        sort(arr_bad.begin(),arr_bad.end(),greater<int>());
        cout <<"array:";display(arr);
        cout <<"good:";display(arr_good);
        cout <<"bad:";display(arr_bad);
    }

    vector<int> getArr(){
        return arr;
    }
    vector<int> getGood(){
        return arr_good;
    }
    vector<int> getBad(){
        return arr_bad;
    }
};


class QuickSort{
    vector<int> arr;
    int cnt_cmp;
    int cnt_swap;
public:
    QuickSort(vector<int> vct):arr(vct){
        cnt_cmp = 0;
        cnt_swap = 0;
    }

    void display(){
        // for(auto a:arr){
        //     cout << a << ' ';
        // }
        cout << endl;
        cout <<"cmp times:"<<cnt_cmp<<endl;
        cout <<"swap times:"<<cnt_swap<<endl;
    }


    void sort(){
        _sort(0,arr.size() - 1);
    }
    void _sort(int left,int right){
        if(++cnt_cmp && left >= right) return;
        int i,j,temp;
        i = left;j = right;
        temp = arr[left];
        
        while (++cnt_cmp &&  i != j)
        {
            while (++cnt_cmp && arr[j] >= temp && i < j){
                j--;
            }
            while (++cnt_cmp && arr[i] <= temp && i < j)
            {
                i++;
            }
            if(++cnt_cmp && i < j){
                ++cnt_swap;
                int t = arr[i];
                arr[i] = arr[j];
                arr[j] = t;
            }
        }
        
        if(left != i){
            ++cnt_swap;
            arr[left] = arr[i];
            arr[i] = temp;
        }
        _sort(left ,i - 1);
        _sort(i + 1 , right);
    }
};

int main(){
    while(1){
        int t;
        cin >> t;
        if (t == 0) break;
        RandInt * r = new RandInt(t,100,1000);

        cout << "test:Normal========================"<<endl;
        QuickSort q1(r->getArr());
        q1.sort();
        q1.display();
        cout << "test:Good========================"<<endl;
        QuickSort q2(r->getGood());
        q2.sort();
        q2.display();
        cout << "test:Bad========================"<<endl;
        QuickSort q3(r->getBad());
        q3.sort();
        q3.display();
    }
    return 0;
}